package permute_combine

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"gitee.com/ljfirst/algo-go-sdk/tools"
	"reflect"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/7 23:28
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 给定不含有重复元素的数组[1,2,3],求所有的排列
 * [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]
 * */
type Permutation struct {
	array []int
	ans   [][]interface{}
}

func (m *Permutation) PermuteMethod(arrayI interface{}) [][]interface{} {
	valueA := reflect.ValueOf(arrayI)
	if valueA.Kind() != reflect.Array && valueA.Kind() != reflect.Slice {
		return nil
	}

	array, err := tools.Interface2IntArray(arrayI)
	if err != nil {
		return nil
	}
	m.array = array
	m.ans = make([][]interface{}, 0)
	ansTemp := make([]int, 0)
	ansTempMap := make(map[int]bool)
	for i := 0; i < len(m.array); i++ {
		ansTemp = append(ansTemp, i)
		ansTempMap[i] = true
		m.roll(ansTemp, ansTempMap)
		ansTemp = make([]int, 0)
		ansTempMap = make(map[int]bool)
	}
	return m.ans
}

func (m *Permutation) roll(ansTemp []int, ansTempMap map[int]bool) {
	if len(ansTemp) == len(m.array) {
		ansValue := make([]interface{}, 0)
		for _, index := range ansTemp {
			ansValue = append(ansValue, m.array[index])
		}
		m.ans = append(m.ans, ansValue)
		return
	}
	for index := 0; index < len(m.array); index++ {
		if ansTempMap[index] { // 存储索引位置，便于去重
			continue
		}
		ansTemp = append(ansTemp, index)
		ansTempMap[index] = true
		m.roll(ansTemp, ansTempMap)
		ansTemp = ansTemp[0 : len(ansTemp)-1]
		ansTempMap[index] = false
	}
	return
}

func (m *Permutation) Tags() []string {
	return []string{C.BackTrack, C.Permutation}
}
